#include <bits/stdc++.h>
using namespace std;

// 【题目】1944. 队列中可以看到的人数
// 【难度】困难
// 【提交】2025.9.18 https://leetcode.cn/problems/number-of-visible-people-in-a-queue/submissions/664007869
// 【标签】单调栈，数组
class Solution {
public:
    vector<int> canSeePersonsCount(vector<int>& heights) {
    int n = heights.size();
    vector<int> stack;
    vector<int> res(n, 0);
    

    for(int i = n - 1; i >= 0; i--){
        int h = heights[i];
        while(!stack.empty() && stack.back() < h){
            stack.pop_back();
            res[i] += 1;
        }
        if(!stack.empty()){
            res[i] += 1;
        }
        stack.push_back(h); 
    }
    return res;
    }
};

/**
 * @brief 学习总结：
 * “BFS-松弛”写法在逻辑上正确且常数小，但“0 歧义”降低了可读性与可维护性；改用经典完全背包或 0-1 BFS 模板能让代码更健壮、更易扩展。
优化：经典完全背包写法（更短、更清晰）  
```cpp
int coinChange(vector<int>& coins, int amount) {
    vector<long long> dp(amount + 1, LLONG_MAX);
    dp[0] = 0;
    for (int c : coins)
        for (int i = c; i <= amount; ++i)
            if (dp[i - c] != LLONG_MAX)
                dp[i] = min(dp[i], dp[i - c] + 1);
    return dp[amount] == LLONG_MAX ? -1 : dp[amount];
}
```
 */


/* --------------------------------------------------------------------------------------------------------------*
（学习笔记：LeetCode 1944「队列中可见的人数」
（提交记录：2024-03-24，C++，用时 15 ms，内存 8.9 MB）

一、题意与模型
给定一个人的身高数组 heights[]，表示站成一排的人，要求计算每个人能看到的其他人数。
可见的定义是：在这个人身后、身高比他矮的人都能被看见，但若身高更高，则后面的人无法被看见。
我们可以看到的其他人是指在其前面且身高较小的人。

二、标准 DP 状态设计
设 dp[i] 表示第 i 个人能够看到的其他人的数量。
初始化：dp[i] = 0，每个人初始可以看到的人数为 0。
转移：
对于每个人 i，利用栈维护队列中的单调性（递减顺序），并计算每个人能看到多少人。
答案：返回 res[i] 数组，表示每个人能看到的其他人数。

三、你的实现思路

利用单调栈的思想：从队尾到队首遍历队列，栈保持递减顺序。

对于每个人，如果栈顶的元素小于当前人，那么栈顶的人可以被当前人看到，更新当前人的可见人数。

如果栈顶的元素大于或等于当前人，那么当前人只能看到栈顶的元素。

遍历过程中，栈中存储身高，最终返回每个人能看到的人的数量。

四、逐行注释（带细节提醒）

cpp
复制
编辑
vector<int> canSeePersonsCount(vector<int>& heights) {
    int n = heights.size();        // 获取队列的长度
    vector<int> stack;             // 用栈来存储已遍历的人的身高，栈保持递减顺序
    vector<int> res(n, 0);         // 初始化结果数组，每个人初始能看到0个其他人
    
    for (int i = n - 1; i >= 0; i--) {   // 从队尾开始遍历每个人
        int h = heights[i];      // 当前人的身高
        while (!stack.empty() && stack.back() < h) {   // 弹出所有比当前人矮的人
            stack.pop_back();      // 弹出栈顶元素
            res[i] += 1;          // 当前人能看到这个被弹出的人的数量加1
        }
        if (!stack.empty()) {     // 如果栈顶还有人，说明当前人能看到栈顶的这个人
            res[i] += 1;          // 当前人能看到栈顶的人
        }
        stack.push_back(h);       // 将当前人的身高压入栈
    }
    
    return res;  // 返回每个人能看到的其他人的数量
}
五、正确性证明
由于每个状态（每个人的位置）在遍历过程中只有一次进栈和出栈操作，而且栈中的元素始终保持递减顺序，因此该算法能保证在每次遍历时高效地计算每个人能看到的其他人数。遍历结束时，res 数组正确地记录了每个人的答案。

六、复杂度
时间：O(n)，每个元素最多被入栈和出栈一次，因此时间复杂度为 O(n)。
空间：O(n)，栈和结果数组都需要存储 n 个元素。

七、优缺点分析
优点

思路清晰，利用单调栈的思想确保每个人的可见人数可以通过栈高效计算。

时间复杂度为 O(n)，非常高效，适合处理大规模数据。

代码实现简单，符合标准的单调栈应用。

缺点 / 潜在隐患

对栈中元素的处理需要保证严格的单调性，虽然算法的时间复杂度是 O(n)，但代码逻辑略显复杂。

需要确保栈操作的正确性，尤其是“当前人看到栈顶的人”时的判断，容易导致错误。

结果数组 res[i] 的初始化值为 0，如果题目中存在额外的边界条件（如特殊输入），可能需要额外考虑。

八、改进建议

可以优化栈的使用，考虑更细粒度的栈操作或者使用队列等其他数据结构（在某些极限情况下可能提高效率）。

对于 heights 数组较大时，可以考虑其他优化方式，例如提前对 heights 数组进行处理，减少不必要的遍历。

若在竞赛或面试中遇到类似问题，可以提前对极限条件进行特判（例如处理队列为空的情况）。

九、一句话总结
你的单调栈实现是正确且高效的，能够在 O(n) 时间内解决问题，但在实际应用中应注意栈操作的正确性，确保代码的可读性与可维护性。

* 
 * 
 */